package com.zy.algorithm.sort;

import org.apache.commons.compress.utils.Lists;

import java.util.List;

/**
 * @author ZhaoYi
 * @date 2023/12/22 9:38
 * <p>
 * 快速排序（Quick Sort）是一种非常高效的排序算法，它采用分而治之的策略来把一个序列分为较小的子序列。
 * ****     选择一个基准元素（pivot），通常是序列中的第一个元素或者最后一个元素。
 * ****     重新排列序列，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆放在基准后面。这个过程称为分区（partitioning）。
 * ****     递归地（recursive）对基准前后的子序列进行步骤1和步骤2的操作。
 * ****     合并所有的分区，即得到排序后的数组。
 */
public class QuickSort<T extends Comparable<? super T>> implements ISort<T> {
    @Override
    public List<T> sort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return list;
        }
        quickSorts(list, 0, list.size() - 1);
        return list;
    }

    private void quickSorts(List<T> list, int star, int end) {
        if (star < end) {
            // 找到分区的下标
            int pi = partitions(list, star, end);
            // 递归对左侧子数组进行快速排序
            quickSorts(list, star, pi - 1);
            // 递归对右侧子数组进行快速排序
            quickSorts(list, pi + 1, end);
        }

    }

    private int partitions(List<T> list, int star, int end) {
        List<T> left = Lists.newArrayList();
        List<T> right = Lists.newArrayList();
        T base = list.get(end);
        for (int i = star; i < end; i++) {
            T t = list.get(i);
            if (t.compareTo(base) > 0) {
                right.add(t);
            } else {
                left.add(t);
            }
        }
        for (int i = 0; i < left.size(); i++) {
            list.set(star + i, left.get(i));
        }
        int size = left.size();
        list.set(star + size, base);
        for (int i = 0; i < right.size(); i++) {
            list.set(star + i + size + 1, right.get(i));
        }


        return star + size;
    }
}
